给定二叉树的中根序列和后根序列，请编写程序创建该二叉树，计算其高度和先根序列，最后删除该二叉树；如给定的中根和后根序列不合法，则亦能识别。

输入格式:

输入为两行字符串，第一行表示某二叉树的后根序列，第二行表示其中根序列。结点的值均为A-Z的大写字母，故二叉树结点个数不超过26，且保证输入的两个序列都是结点的全排列，但不一定是合法的中根和后根序列。

输出格式:

如果输入的序列不合法（不是同一棵树的中根序列和后根序列），则输出INVALID。若输入序列合法，输出为两行，第一行为一个整数，表示该二叉树的高度，第二行为一个字符串，表示该二叉树的先根序列。

输入样例1:

1
2
CEFDBHGA
CBEDFAGH

输出样例1:

1
2
3
ABCDEFGH

输入样例2:

1
2
CBEDFAGH
CEFDBHGA

输出样例2:

1
INVALID

输入样例3:

1
2
BCA 
CAB

输出样例3:

1
INVALID

思路：

· 检测输入的后序+中序是否为同一棵树：使用bool check(string str1,string str2)函数判断两个序列全部子树所对应的左子树、根、右子树是否分别长度相等且含有同样的元素。若满足条件的返回1，否则返回0。

· 根据后序+中序求二叉树的高度：使用int GetHeight(int root,int start,int end)函数递归求解，需要注意的是此题貌似认为空树深度为-1…玄学

后序(左右根)最后出现的是根结点，根据根结点划分中序序列将其分为左右子树来求高度

root为当前后序的根结点下标(根据当前的中序序列可以把当前的中序分为左根右)
start为当前中序序列起始位置
end为当前中序序列结束位置

树的高度 = max{左子树高度，右子树高度}+1

· 根据后序+中序输出先序：使用void pre(int root,int start,int end)函数递归求解

后序(左右根)最后出现的是根结点，输出根。k为当前中序序列的根结点位置，根据k分割中序序列左右子树的下标，递归求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
vector<char> post,in;
bool check(string str1,string str2) { 
    if(!str1.length()&&!str2.length()) return true;
    if(str1.length()!=str2.length()) return false;
    char root = str1[str1.length()-1];
    int k;
    for(k=0;k<str2.length();k++) {
        if (root==str2[k])
            break;
    }
    string str1l = str1.substr(0,k);
    string str1r = str1.substr(k, str1.length() - 1 - k);
    string str2l = str2.substr(0,k);
    string str2r = str2.substr(k+1);
    for (int i=0;i<str1l.length();i++) {
        if (str2l.find(str1l[i])==str2l.npos) return false;
    }
    for (int i=0;i<str1r.length();i++) {
        if (str2r.find(str1r[i])==str2r.npos) return false;
    }
    return check(str1l,str2l)&&check(str1r,str2r);
}
void pre(int root,int start,int end){
	if(start>end) return;
	int k;
	for(k=start;k<end;k++)
		if(in[k]==post[root]) break;
	cout << post[root];	
	pre(root-1-end+k,start,k-1);
	pre(root-1,k+1,end);
}
int GetHeight(int root,int start,int end){
	if(start<=end){
		int k;
		for(k=start;k<end;k++){
			if(in[k]==post[root]) break;
		}
		int hl = GetHeight(root-1-end+k,start,k-1);  
		int hr = GetHeight(root-1,k+1,end);  
        return max(hl,hr)+1;  
	}else return -1;  //这题貌似认为空树深度为-1...
}
int main(){
	string str1="",str2="";
	cin >> str1 >> str2;
	for(int i=0;i<str1.size();i++){
		if(str1[i]>='A'&&str1[i]<='Z') post.push_back(str1[i]);
	} 
	for(int i=0;i<str2.size();i++){
		if(str2[i]>='A'&&str2[i]<='Z') in.push_back(str2[i]);
	} 
	if(check(str1,str2)){
        int N = post.size();
		cout << GetHeight(N-1,0,N-1) << endl;
		pre(N-1,0,N-1);
	}else cout << "INVALID";
	return 0;
}